package 中等.搜索.回溯;

/**
 * 你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，
 * 并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数
 * 就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。
 * <p>
 * 为了使收益最大化，矿工需要按以下规则来开采黄金：
 * <p>
 * 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
 * 矿工每次可以从当前位置向上下左右四个方向走。
 * 每个单元格只能被开采（进入）一次。
 * 不得开采（进入）黄金数目为 0 的单元格。
 * 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/path-with-maximum-gold
 */
public class 黄金矿工_1219 {

    private int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  //定义四个方向，上下左右
    private int rows, columns;
    private int ans;  //力扣坑，static变量会出bug

    public static void main(String[] args) {

        int[][] gird = {{34, 0, 1, 0, 0, 0}, {0, 0, 2, 0, 1, 0}, {5, 4, 3, 7, 4, 2}, {0, 0, 5, 0, 1, 4}, {0, 0, 5, 0, 2, 3}};
        System.out.println(new 黄金矿工_1219().getMaximumGold(gird));

    }

    /**
     * 每个单元格只能被开采（进入）一次。
     * 意味着需要用到深度搜索
     * 回溯算法
     *
     * @param grid
     * @return
     */
    public int getMaximumGold(int[][] grid) {
        rows = grid.length;
        columns = grid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (grid[i][j] != 0) {  //矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止
                    dfsSearch(i, j, 0, grid);
                }
            }
        }
        return ans;
    }

    public void dfsSearch(int curRow, int curColumn, int curAns, int[][] grid) {
        int curValue = grid[curRow][curColumn];
        if (curValue == 0) {  //递归终止条件
            ans = Math.max(ans, curAns);  //每停止一次就是一次新的路径，一个答案
            return;
        }
        curAns += curValue;  //在下去的时候，就已经将黄金累加好了，return时无需计算
        grid[curRow][curColumn] = 0;  //一条路走到黑
        for (int[] direct : direction) {
            int nextRow = curRow + direct[0];
            int nextColumn = curColumn + direct[1];
            if (nextRow >= 0 && nextRow < rows && nextColumn >= 0 && nextColumn < columns) {
                dfsSearch(nextRow, nextColumn, curAns, grid);
            }
        }
        grid[curRow][curColumn] = curValue;  //还原黄金
    }

}
